package leetcode.operateSystem.p460;

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;

class LFUCache {
    private int capacity;
    private int size;
    private HashMap<Integer, Integer[]> map;

    public LFUCache(int capacity) {
        this.capacity = capacity;
        this.map = new HashMap<>(10000);
    }
    
    public int get(int key) {
        Integer[] value = null;
        if(capacity == 0 || (value = map.get(key)) == null) return -1;
        // 每次get后需要给对应的ctn加1，所有value[2]都要加1
        value[1]++; // 被访问以后value[1]会加1，即使用次数加了1
        timeIncrement();
        value[2]=0;
        return value[0];
    }

    // 所有的key的未使用时间都加1
    private void timeIncrement() {
        // 遍历所有key，将未使用时间都加1
        for (Map.Entry<Integer, Integer[]> entry : map.entrySet()) {
            entry.getValue()[2]++;
        }
    }
    
    public void put(int key, int value) {
        if (capacity == 0) {
            return;
        }
        // 查看key是否存在
        else if (map.containsKey(key)) {
            // 修改对应的value
            map.get(key)[0] = value;
            timeIncrement();
            // 时间清零
            map.get(key)[2] = 0;
        } else {
            // 容量满了，需要移除最不经常使用的元素
            if (size == capacity) {
                removeLFUElement();
            }
            timeIncrement();
            size++;
            map.put(key, new Integer[] {value, 1, 0});
        }
    }

    // 移除最不经常使用的元素
    private void removeLFUElement() {
        // 遍历所有key，找出最不经常使用的元素
        Set<Map.Entry<Integer, Integer[]>> entries = map.entrySet();
        Iterator<Map.Entry<Integer, Integer[]>> entryIterator = entries.iterator();
        Map.Entry<Integer, Integer[]> lfuEntry = entryIterator.next();

        // 找cnt最短的entry，如果cnt相等，那么就比较time，去time较大者
        while (entryIterator.hasNext()) {
            Map.Entry<Integer, Integer[]> entry = entryIterator.next();
            if (lfuEntry.getValue()[1] > entry.getValue()[1]) {
                lfuEntry = entry;
            } else if (lfuEntry.getValue()[1] == entry.getValue()[1]) {
                if (lfuEntry.getValue()[2] < entry.getValue()[2]) {
                    lfuEntry = entry;
                }
            }
        }

        map.remove(lfuEntry.getKey());
        size--;
    }

    private void printMap() {
        for (Map.Entry<Integer, Integer[]> entry : map.entrySet()) {
            Integer[] values = entry.getValue();
            System.out.print("[key: " + entry.getKey() + ", value: " + values[0] + ", cnt: " + values[1] + ", time: " + values[2] + "] ");
        }
    }

    private void putAndPrint(int key, int value) {
        System.out.print("lfu.put(" + key + ", " + value + ")------");
        put(key, value);
        printMap();
        System.out.println();
    }

    private void getAndPrint(int key) {
        System.out.print("lfu.get(" + key + ") = " + get(key) + "-------");
        printMap();
        System.out.println();
    }

    public static void main(String[] args) {
        // 测试用例1
        /*LFUCache lfu = new LFUCache(2);
        lfu.putAndPrint(1, 1);   // cache=[1,_], cnt(1)=1
        lfu.putAndPrint(2, 2);   // cache=[2,1], cnt(2)=1, cnt(1)=1
        // cache=[1,2], cnt(2)=1, cnt(1)=2
        lfu.getAndPrint(1);
        lfu.putAndPrint(3, 3);   // 去除键 2 ，因为 cnt(2)=1 ，使用计数最小
        // cache=[3,1], cnt(3)=1, cnt(1)=2
        lfu.getAndPrint(2);
        // cache=[3,1], cnt(3)=2, cnt(1)=2
        lfu.getAndPrint(3);
        lfu.putAndPrint(4, 4);   // 去除键 1 ，1 和 3 的 cnt 相同，但 1 最久未使用
        // cache=[4,3], cnt(4)=1, cnt(3)=2
        lfu.get(1);
        // cache=[3,4], cnt(4)=1, cnt(3)=3
        lfu.getAndPrint(3);
        // cache=[3,4], cnt(4)=2, cnt(3)=3
        lfu.getAndPrint(4);*/

        // 测试用例2
        // ["LFUCache","put","put","get","get","get","put","put","get","get","get","get"]
        // [[3],[2,2],[1,1],[2],[1],[2],[3,3],[4,4],[3],[2],[1],[4]]
        /*LFUCache lfu = new LFUCache(3);
        lfu.putAndPrint(2, 2);
        lfu.putAndPrint(1, 1);
        lfu.getAndPrint(2); // 2
        lfu.getAndPrint(1); // 1
        lfu.getAndPrint(2); // 2
        lfu.putAndPrint(3, 3);
        lfu.putAndPrint(4, 4);
        lfu.getAndPrint(3); // -1
        lfu.getAndPrint(2); // 2
        lfu.getAndPrint(1); // 1
        lfu.getAndPrint(4); // 4*/

        // 测试用例3
        // ["LFUCache","put","put","put","put","get"]
        // [[2],[3,1],[2,1],[2,2],[4,4],[2]]
        /*LFUCache lfuCache = new LFUCache(2);
        lfu.putAndPrint(3, 1);
        lfu.putAndPrint(2, 1);
        lfu.putAndPrint(2, 2);
        lfu.putAndPrint(4, 4);
        lfu.getAndPrint(2);*/

        // 测试用例4
        // ["LFUCache","put","get"]
        // [[0],[0,0],[0]]
        /*LFUCache lfu = new LFUCache(0);
        lfu.putAndPrint(0, 0);
        lfu.getAndPrint(0);*/

        // 测试用例5
        // ["LFUCache","put","put","get","put","put","get"]
        // [[2],[2,1],[2,2],[2],[1,1],[4,1],[2]]
        /*FUCache lfu = new LFUCache(2);
        lfu.putAndPrint(2, 1);
        lfu.putAndPrint(2, 2);
        lfu.getAndPrint(2);
        lfu.putAndPrint(1, 1);
        lfu.putAndPrint(4, 1);
        lfu.getAndPrint(2);*/
        // 测试用例6
        // ["LFUCache","put","put","put","put","get","get"]
        // [[2],[2,1],[1,1],[2,3],[4,1],[1],[2]]
        LFUCache lfu = new LFUCache(2);
        lfu.putAndPrint(2, 1);
        lfu.putAndPrint(1, 1);
        lfu.putAndPrint(2, 3);
        lfu.putAndPrint(4, 1);
        lfu.getAndPrint(1);
        lfu.getAndPrint(2);

        // 测试用例7
        // ["LFUCache","put","put","put","put","put","get","put","get","get","put","get","put","put","put","get","put","get","get","get","get","put","put","get","get","get","put","put","get","put","get","put","get","get","get","put","put","put","get","put","get","get","put","put","get","put","put","put","put","get","put","put","get","put","put","get","put","put","put","put","put","get","put","put","get","put","get","get","get","put","get","get","put","put","put","put","get","put","put","put","put","get","get","get","put","put","put","get","put","put","put","get","put","put","put","get","get","get","put","put","put","put","get","put","put","put","put","put","put","put"]
        // [[10],[10,13],[3,17],[6,11],[10,5],[9,10],[13],[2,19],[2],[3],[5,25],[8],[9,22],[5,5],[1,30],[11],[9,12],[7],[5],[8],[9],[4,30],[9,3],[9],[10],[10],[6,14],[3,1],[3],[10,11],[8],[2,14],[1],[5],[4],[11,4],[12,24],[5,18],[13],[7,23],[8],[12],[3,27],[2,12],[5],[2,9],[13,4],[8,18],[1,7],[6],[9,29],[8,21],[5],[6,30],[1,12],[10],[4,15],[7,22],[11,26],[8,17],[9,29],[5],[3,4],[11,30],[12],[4,29],[3],[9],[6],[3,4],[1],[10],[3,29],[10,28],[1,20],[11,13],[3],[3,12],[3,8],[10,9],[3,26],[8],[7],[5],[13,17],[2,27],[11,15],[12],[9,19],[2,15],[3,16],[1],[12,17],[9,1],[6,19],[4],[5],[5],[8,1],[11,7],[5,2],[9,28],[1],[2,2],[7,4],[4,22],[7,24],[9,26],[13,28],[11,26]]
    }
}

/**
 * Your LFUCache object will be instantiated and called as such:
 * LFUCache obj = new LFUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */